Chính quyền Nguyễn Khánh đã rất muốn đẩy nhanh việc tử hình Nguyễn Văn Trỗi vào cuối tháng 8 năm 1964. Tuy nhiên, việc này phải tạm ngưng lại vì sau ngày 25 tháng 8 năm 1964, các phong trào biểu tình chống Nguyễn Khánh tình hình chính trị bất ổn, các cuộc binh biến diễn ra liên tiếp.

Tài liệu biên bản Hội đồng ân xá ngày 17/6/1964 cho biết Hội đồng ân xá nhóm họp tại phòng Bộ Tư pháp, số 47 đại lộ Thống Nhất Sài Gòn vào lúc 17h ngày 17/8/1964 để xét các đề nghị ân xá và bày tỏ ý kiến về các khoản ân giảm cho phạm nhân được hưởng. Trong phiên họp này, Hội đồng ân xá xem xét hồ sơ xin ân xá của 4 tội nhân, trong đó có anh Nguyễn Văn Trỗi. Tài liệu này cũng cho biết anh Trỗi sinh năm 1940 tại xã Thanh Quýt, quận Điện Bàn (Quảng Nam), thợ điện, con của Nguyễn Văn Hòa và Nguyễn Thị Tuất, có vợ, không có tiền án.

“

Ngày 9/5/1964, nhờ có mật báo, cảnh sát quận 3 đã bắt được Nguyễn Văn Trỗi đang chuyền dây điện cho một tên Việt cộng dưới ao rau muống gần cầu Công Lý. Nguyễn Văn Trỗi thú nhận đã gia nhập tổ chức Việt cộng khu Sài Gòn - Gia Định do Lê Đức Hiền làm tổ trưởng và chính Trỗi đã dụ được Nguyễn Hữu Lời gia nhập tổ chức. Ngày 7/5/1964, y đã nhận được của Lê Đức Hiền 800 USD để mua dây điện và 16 cục pin dùng để giật mìn phá cầu Công Lý trong dịp Bộ trưởng Quốc phòng Hoa Kỳ Mac Namara sang Việt Nam. Ngày 11/5/1964, Nguyễn Hữu Lời có phận sự xuống ao rau muống kéo dây điện cột vào cây dừa cách cầu 100 thước. Còn Lê Đức Hiền lo việc đặt mìn và nối dây điện vào khối pin 72W cho nổ. Nguyễn Văn Trỗi và Nguyễn Hữu Lời bị bắt quả tang khi đang thi hành công tác phá hoại nói trên. Tại nha cảnh sát Đô Thành, chúng xác nhận đã hành động như trên, Nguyễn Văn Trỗi nhảy qua cửa sổ tầng lầu 2 để tự vẫn, nhưng chỉ bị trầy xương chân mặt mà thôi. Trước tòa án Quân sự Mặt trận Vùng 3 Chiến Thuật, ngày 10/8/1964, Nguyễn Văn Trỗi và Nguyễn Hữu Lời đã xác nhận những hành động của chúng.

”

“

Tòa đã tuyên xử: Nguyễn Văn Trỗi tử hình và tịch thu toàn bộ tài sản về tội phản nghịch, toan phá hủy và toan mưu sát… Sau khi xem xét, Hội đồng ân xá đề nghị bác đơn xin ân xá của Nguyễn Văn Trỗi, vì việc bảo vệ an ninh cho chánh khách các quốc gia bạn của Việt Nam Cộng hòa cần được thực hiện một cách hữu hiệu bằng cách thực hành bản án tử hình tên Việt cộng này.

”

[12]

Sau đó, chính quyền Nguyễn Khánh định tử hình anh Trỗi vào ngày 7 tháng 10 năm 1964. Biết tin này, nhóm "Biệt đội du kích quân" chống chế độ thân Mỹ tại Venezuela đã đề nghị trao đổi con tin là sĩ quan Mỹ Michael Smolen bị họ bắt cóc ở Caracas. Tuy 2 bên đã có sự thỏa thuận, nhưng sau khi Michael Smolen được thả, chính phủ Sài Gòn đã xé bỏ thỏa thuận và đưa Nguyễn Văn Trỗi đi xử bắn bí mật tại sân sau nhà lao Khám Chí Hòa lúc 9 giờ 45 phút ngày 15 tháng 10 năm 1964[2], trước sự chứng kiến của nhiều phóng viên nước ngoài[13].

Trước khi bị xử tử, anh đã hô lớn: "Hãy nhớ lấy lời của tôi! Đả đảo đế quốc Mỹ! Đả đảo Nguyễn Khánh! Hồ Chí Minh muôn năm! Việt Nam muôn năm!"[14] Tờ báo Miami News (Hoa Kỳ) ngày 15 tháng 10 năm 1964 đã có bài tường thuật vụ xử bắn[14][15]:

Người điệp viên Việt Cộng 24 tuổi (tức Nguyễn Văn Trỗi) đã hô to những khẩu hiệu "Hồ Chí Minh muôn năm!", "Mỹ - Ngụy hãy cút khỏi Việt Nam". Trỗi bị giải ra pháp trường nơi có 12 tay súng của Cảnh sát Quốc gia Việt Nam Cộng hòa và Quân lực Việt Nam Cộng hòa chờ sẵn. Sau khi liên tục hô vang những lời đả kích đế quốc Mỹ, đả kích chính quyền tay sai (tức Việt Nam Cộng hòa) và Nguyễn Khánh, người thanh niên hô lớn lời chào vĩnh biệt dành cho Hồ Chí Minh, Chủ tịch nước Việt Nam Dân chủ Cộng hòa. Trỗi đã từ chối bịt mắt trước khi bị bắn, tuy nhiên đến phút chót, đội thi hành án quyết định bịt mắt anh lại.